package Exercises;/*
 *
 * @author 陈粒
 * @version 创建时间：2021/7/5 10:40
 */
import java.util.*;
/**
 折半查找/二分查找非递归版
 */
public class Half_search {
    public static void main(String[] args) {
        int a[] = suiji();
        Arrays.sort(a);
        System.out.println("随机生成的10个数分别为：" + Arrays.toString(a));
        System.out.print("请输入要查找的数：");
        int key = new Scanner(System.in).nextInt();
        int result = Binary_Search(a, key);
        if (key == a[result]) {
            System.out.println("找到了该数，" + "该数的位置在数组的第" + (result + 1) + "个位置");
        } else {
            System.out.println("没有找到该数");
        }
    }
    /*
    折半查找的方法
     */
    public static int Binary_Search(int[] a, int key) {
        int mid, low = 0, high = a.length - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < a[mid]) {
                high = mid - 1;
            } else if (key > a[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -(a[low] + 1);
    }

    /*
    用于随机生成数组
     */
    public static int[] suiji() {
        int a[] = new int[10];
        for (int i = 0; i < 10; i++) {
            a[i] = new Random().nextInt(100) + 1;
        }
        return a;
    }
}

